package List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 故我
 * Date: 2024-02-01
 * Time: 11:39
 */
public class MyList implements IList {

    static class ListNode {
        private int val;
        private ListNode prev; // 前驱
        private ListNode next; // 后继

        public ListNode(int val) {
            this.val = val;
        }
    }

    // 头节点 与 尾节点
    private ListNode head;
    private ListNode tail;

    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    @Override
    public void addIndex(int index, int data) {
        ListNode cur = head;
        ListNode node = new ListNode(data);
        if (index < 0 || index > size()) {
            System.out.println("下标不合法!");
            return;
        }

        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }

        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
        node.next = cur;

    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                return true;
            }
        }
        return false;
    }

    @Override
    public void remove(int key) {
        // 去遍历删除
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    // 此时为头删
                    head = head.next;
                    // 判断是否只有一个头节点
                    if (head == null) {
                        tail = null;
                    } else {
                        // 此时就不是只有一个节点
                        head.prev = null;
                    }
                } else {
                    // 此时这个cur就不是头节点
                    cur.prev.next = cur.next;
                    if (cur.next == null) {
                        // 说明这个是尾节点
                        tail = tail.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }

                }
                return; // 表示删除完
            } else {
                cur = cur.next;
            }
        }
    }

    @Override
    public void removeAllKey(int key) {
        // 去遍历删除
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == key) {
                if (cur == head) {
                    // 此时为头删
                    head = head.next;
                    // 判断是否只有一个头节点
                    if (head == null) {
                        tail = null;
                    } else {
                        // 此时就不是只有一个节点
                        head.prev = null;
                    }
                } else {
                    // 此时这个cur就不是头节点
                    cur.prev.next = cur.next;
                    if (cur.next == null) {
                        // 说明这个是尾节点
                        tail = tail.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

    @Override
    public int size() {
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }

        return count;
    }

    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.prev = null;
            cur.next = null;
            cur = cur.next;
        }
        head = null;
        tail = null;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
